package com.aigis.big4.tmp.javase.Sort;

public class Select {
    public static void main(String[] args) {

        int[] array = {4, 2, 8, 9, 5, 7, 6, 1, 3};
        System.out.println();
        // --------------------选择排序--------------------------
        // O(N2) 快于冒泡
        int N = array.length;

        for (int i = 0; i < N; i++) {
            int min = i;
            for (int j = i; j < N; j++) {
                if (array[j] < array[min]) {
                    min = j;
                }
            }
            int temp = array[i];
            array[i] = array[min];
            array[min] = temp;
        }
        //输出排序结果
        for (int i = 0; i < N; i++) {
            System.out.print(array[i] + " ");
        }


        // --------------------插入排序--------------------------
        // 平均性能最好

        System.out.println("\n插入sort");
        for (int i = 1; i < N; i++) {
            int j = i;
            while (j > 0 && array[i] < array[j - 1]) {
                array[j] = array[j - 1];
                j--;
            }
            array[j] = array[i];
        }


        //输出排序结果
        for (int i = 0; i < N; i++) {
            System.out.print(array[i] + " ");
        }

    }


}
